package com.icexxx.prime;

public class Main5 {
    public static final int[] ppArray = { 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
            89, 97 };

    public static void main(String[] args) {
        int n = 1000000000;
        long t1 = System.currentTimeMillis();
        final int[] nums = { 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2,
                4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10 };
        int count = 25;
        int base = 11;
        int i = base;
        int nn = (n - base) / 210;
        for (int m = 0; m < nn; m++) {
            for (int j = 0; j < nums.length; j++) {
                int increment = nums[j];
                int z = i + increment;
                if (isPrimeByArray(z)) {
                    count++;
                }
                i = z;
            }
        }
        for (int j = i; j < n; j = j + 2) {
            if (isPrimeRest(j)) {
                count++;
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("count=" + count);
        System.out.println("time=" + (t2 - t1));
    }

    private static boolean isPrimeByArray(int num) {
        for (int i = 0; i < ppArray.length; i++) {
            if (num % ppArray[i] == 0) {
                return false;
            }
        }
        int s = (int) (Math.sqrt(num) + 1);
        for (int i = 101; i < s; i = i + 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    private static boolean isPrimeRest(int num) {
        int s = (int) (Math.sqrt(num) + 1);
        for (int i = 2; i < s; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

}
//count=664579
//time=5203
//count=5761455
//time=153520
//count=50847534
//time=4515977
